package 算法.lib;

/*给你一个下标从 0 开始的整数数组 nums ，以及整数 modulo 和整数 k 。
请你找出并统计数组中 趣味子数组 的数目。
如果 子数组 nums[l..r] 满足下述条件，则称其为 趣味子数组 ：
在范围 [l, r] 内，设 cnt 为满足 nums[i] % modulo == k 的索引 i 的数量。并且 cnt % modulo == k 。
以整数形式表示并返回趣味子数组的数目。
注意：子数组是数组中的一个连续非空的元素序列。 */

import java.util.*;

public class CountInterestingSubarrays {
    public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
        long result = 0;
        int n = nums.size();
        int prefixSum = 0;
        HashMap<Integer, Integer> countMap = new HashMap<>();
        countMap.put(0, 1); // 初始化前缀和为 0 的计数

        for (int i = 0; i < n; i++) {
            // 如果 nums[i] % modulo == k，则将其视为 1，否则视为 0
            if (nums.get(i) % modulo == k) {
                prefixSum++;
            }
            prefixSum %= modulo;

            // 计算目标前缀和
            int target = (prefixSum - k + modulo) % modulo;

            // 如果目标前缀和存在于 map 中，则累加其出现次数
            result += countMap.getOrDefault(target, 0);

            // 更新当前前缀和的计数
            countMap.put(prefixSum, countMap.getOrDefault(prefixSum, 0) + 1);
        }

        return result;
    }
}
